package 中等.模拟;

/**
 * 一个 ATM 机器，存有 5 种面值的钞票：20 ，50 ，100 ，200 和 500 美元。初始时，ATM 机是空的。用户可以用它存或者取任意数目的钱。
 * 取款时，机器会优先取 较大 数额的钱。
 * 比方说，你想取 $300 ，并且机器里有 2 张 $50 的钞票，1 张 $100 的钞票和1 张 $200 的钞票，那么机器会取出 $100 和 $200 的钞票。
 * 但是，如果你想取 $600 ，机器里有 3 张 $200 的钞票和1 张 $500 的钞票，那么取款请求会被拒绝，因为机器会先取出 $500 的钞票，然后无法取出剩余的 $100 。注意，因为有 $500 钞票的存在，机器 不能 取 $200 的钞票。
 * 请你实现 ATM 类：
 * ATM() 初始化 ATM 对象。
 * void deposit(int[] banknotesCount) 分别存入 $20 ，$50，$100，$200 和 $500 钞票的数目。
 * int[] withdraw(int amount) 返回一个长度为 5 的数组，分别表示 $20 ，$50，$100 ，$200 和 $500 钞票的数目，并且更新 ATM 机里取款后钞票的剩余数量。如果无法取出指定数额的钱，请返回 [-1] （这种情况下 不 取出任何钞票）。
 *
 * @ https://leetcode.cn/problems/design-an-atm-machine/?envType=daily-question&envId=2025-01-05
 * @date 2025/01/05
 */
public class 设计一个ATM机器_2241 {

    public static void main(String[] args) {

    }

    /**
     * 使用数组存储每个面值的数量模拟+二分查找面值大的钞票可以取出的数量
     */
    static class ATM {

        private int[] money = new int[]{20, 50, 100, 200, 500};
        private int[] cnt = new int[5];

        public ATM() {

        }

        public void deposit(int[] banknotesCount) {
            for (int i = 0; i < banknotesCount.length; i++) {
                cnt[i] += banknotesCount[i];
            }
        }

        public int[] withdraw(int amount) {
            int[] tempCnt = new int[5];
            for (int i = 0; i < tempCnt.length; i++) {
                tempCnt[i] = cnt[i];
            }
            int[] ans = new int[5];
            int curAmount = amount;

            for (int i = ans.length - 1; i >= 0; i--) {

                int curCnt = binarySearch(tempCnt[i], money[i], curAmount);
                ans[i] = curCnt;
                curAmount -= curCnt * money[i];
                tempCnt[i] -= curCnt;
            }
            // 回退
            if (curAmount > 0) {
                return new int[]{-1};
            }
            cnt = tempCnt;
            return ans;
        }

        // 面额为money的数量有maxCnt，二分查找 n*money <= amount (n<=MaxCnt)的最大 n 值
        private int binarySearch(int maxCnt, long money, int amount) {
            int ans = maxCnt;
            int left = 0, right = maxCnt;
            while (left <= right) {
                int mid = left + (right - left) / 2;
                // long 防止数字溢出
                if (mid * money <= amount) {
                    ans = mid;
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
            return ans;
        }
    }

}
